package org.hhchat.leetcode.hashtable;

/**
 * Created this one by HMH on 2017/9/28.
 */
public class code204_easy {

    static class Solution {
        public int countPrimes(int n) {
            boolean[] notPrime = new boolean[n];
            int count = 0;
            for (int i = 2; i < n; i++) {
                if (notPrime[i] == false) {
                    count++;
                    for (int j = 2; i*j < n; j++) {
                        notPrime[i*j] = true;
                    }
                }
            }

            return count;
        }
    }


    public static void main(String[] args){
        Solution solution = new Solution();
        System.out.println(solution.countPrimes(1500000));
    }

}
